package 常见经典递归过程解析;

import java.util.Stack;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
public class Code06_SortStackWithRecursive {

    public static void sort(Stack<Integer> stack) {
        int deep = deep(stack);
        while(deep > 0){
            int max = max(stack, deep);
            int times = maxTimes(stack, deep, max);
            down(stack, deep, max, times);
            deep -= times;
        }
    }

    // 返回栈的深度
    // 不改变栈的数据状况
    public static int deep(Stack<Integer> stack){
        if(stack.isEmpty()){
            return 0;
        }else {
            int num = stack.pop();
            int deep = deep(stack) + 1;
            stack.push(num);
            return deep;
        }
    }

    // 从栈当前的顶部开始，往下数deep层
    // 返回这deep层里的最大值
    public static int max(Stack<Integer> stack, int deep){
        if(deep == 0){
            return Integer.MIN_VALUE;
        }else {
            int num = stack.pop();
            int restMax = max(stack, deep - 1);
            int max = Math.max(num, restMax);
            stack.push(num);
            return max;
        }
    }

    // 从栈当前的顶部开始，往下数deep层，已知最大值是max了
    // 返回，max出现了几次，不改变栈的数据状况
    public static int maxTimes(Stack<Integer> stack, int deep, int max){
        if(deep == 0){
            return 0;
        }else {
            int num = stack.pop();
            int restTimes = maxTimes(stack, deep - 1, max);
            int times = restTimes + (num == max ? 1 : 0);
            stack.push(num);
            return times;
        }
    }

    // 从栈当前的顶部开始，往下数deep层，已知最大值是max，出现了k次
    // 请把这k个最大值沉底，剩下的数据状况不变
    public static void down(Stack<Integer> stack, int deep, int max, int times){
        if(deep == 0){
            for(int i = 0; i < times; i++){
                stack.push(max);
            }
        }else {
            int num = stack.pop();
            down(stack, deep - 1, max, times);
            if(num != max){
                stack.push(num);
            }
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(1);
        stack.push(5);
        stack.add(4);
        stack.add(6);
        stack.add(9);
        stack.add(5);
        stack.add(6);
        stack.add(10);
        sort(stack);
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }

    }

}
